
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1659. -- [Usaco2006 Mar]Lights Out -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1659: [Usaco2006 Mar]Lights Out</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>31&nbsp;&nbsp;<span class=green>Solved: </span>27<br>[<a href='submitpage.php?id=1659'>Submit</a>][<a href='problemstatus.php?id=1659'>Status</a>][<a href='bbs.php?id=1659'>Discuss</a>]</center><h2>Description</h2><div class=content>
The cows so much prefer to sleep in the dark. Every night, though,
when they return to the barn, some of the L (3 <= L <= 50) lights
are switched on. They know the location of the push button switches
but, as is always the problem, they lack fingers. The buttons are
arranged in a nice row, and the left most button (#1) toggles light
#1; the next button to the right toggles light #2; and so on.
('Toggle' means change from off-to-on or on-to-off, depending on
the current state of the switch.)

They do however have an unusual pitchfork with T (1 <= T <= 7)
slots, each one of which might hold a tine that can push the switches.
Some tines are present; some might be absent. By way of example,
imagine a pitchfork with T=4 and a missing tine. This particular
pitchfork has tines in the 1st, 2nd, and 4th positions, easily
described as '1101'.

If the pitchfork is aimed at the leftmost switch, then lights #1,
#2, and #4 are toggled (#3 isn't toggled since there is no tine
there). If the pitchfork is aimed at switch #3, then lights #3, #4,
and #6 are toggled. The pitchfork must be aimed so that all its
tine slots touch switches; the fork cannot cross the end of the line of
switches.

Given a list of lights that are on and a configuration for a
pitchfork, determine a sequence of pitchfork presses that will
toggle the lights until the minimum number of lights is lit.
</div><h2>Input</h2><div class=content>
* Line 1: Two space-separated integers: L and T

* Line 2: A line with L characters (and no spaces), each of which is
        '0' or '1'. '1' means a light in that slot is lit; '0' means
        the light in that slot is not lit.

* Line 3: A line with T characters, each of which is '0' or '1' (no
        spaces are present). '1' means a tine is present on the
        pitchfork in that slot; '0' means otherwise.  The pitchfork
        can not be inverted.

</div><h2>Output</h2><div class=content>* Line 1: K, the number of positions at which the pitchfork was aimed.

* Lines 2..K+1: Each line contains a single integer X (1 <= X <=
        L-T+1) that tells where the pitchfork was aimed (the leftmost
        tine slot, that is) to toggle some lights. A program will
        evaluate the decisions to simulate toggling the lights.  Full
        credit is given for minimal-length solutions that leave to the
        minimum number of lights turned on; partial credit for
        solutions that take longer to minimize the lights. It is not
        always possible switch all the lights off.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>10 4<br />
1111111111<br />
1101<br />
<br />
INPUT DETAILS:<br />
<br />
All 10 lights all on; three of four tines are present on the pitchfork<br />
(tine #3 is missing)<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
5<br />
3<br />
1<br />
4<br />
7<br />
6<br />
<br />
OUTPUT DETAILS:<br />
<br />
1111111111  Start<br />
1100101111  Toggle 3<br />
0001101111  Toggle 1<br />
0000000111  Toggle 4<br />
0000001010  Toggle 7<br />
0000010000  Toggle 6<br />
One light remaining is the best one can do.  Many other solutions<br />
will leave one light lit (possibly a different light).<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1659'>Submit</a>][<a href='problemstatus.php?id=1659'>Status</a>][<a href='bbs.php?id=1659'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
